package basic.courseLearn08;

import org.junit.Test;

//关于前缀树的相关操作
public class PrefixTreeUtil {

    private PrefixTreeNode root;    //前缀树的根节点

    //初始化前缀树
    public void initPrefixTree() {
        root = new PrefixTreeNode();
    }

    //插入前缀树
    public void insert(String word) {
        //1. 从根节点开始
        PrefixTreeNode current = root;
        //2. 遍历word的每一个字符
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            //2.1 判断当前字符是否已经存在
            if (current.nexts[index]==null){    //不存在,新建节点
                current.nexts[index] = new PrefixTreeNode();
                current.pass++;
            }else{    //存在,pass++
                current.pass++;
            }
            //2.2 移动到下一个节点
            current = current.nexts[index];
        }
        //3. 最后字符的end++
        current.end++;
        current.pass++;
    }

    //删除前缀树
    public void delete(String word) {
        //1. 从根节点开始
        PrefixTreeNode current = root;
        //2. 判断该字符串是否存在
        if (query(word) == 0) {    //不存在,直接返回
            return;
        }
        //3. 遍历word的每一个字符
        for (int i = 0; i < word.length(); i++) {
            //3.1 获取当前字符的索引
            int index = word.charAt(i) - 'a';
            //3.2 判断当前字符是否存在
            current.pass--;    //pass--
            if (current.pass == 1){
                current.nexts[index]=null;    //删除节点
            }
            //3.3 移动到下一个节点
            current = current.nexts[index];    //移动到下一个节点
        }
        current.end--;    //end--
    }

    //查询字符串出现次数
    public int query(String word) {
        //1. 从根节点开始
        PrefixTreeNode current = root;
        //2. 遍历word的每一个字符
        for (int i = 0; i < word.length(); i++) {
            //2.1 获取当前字符的索引
            int index = word.charAt(i) - 'a';
            //2.2 判断当前字符是否存在
            if (current.nexts[index] == null) {    //不存在,直接返回0
                return 0;
            }else{
                current = current.nexts[index];    //移动到下一个节点
            }
        }
        return current.end;    //返回end值
    }

    //查询以指定字符串为前缀的次数
    public int queryPrefix(String prefix) {
        //1. 从根节点开始
        PrefixTreeNode current = root;
        //2. 遍历prefix的每一个字符
        for (int i = 0; i < prefix.length(); i++) {
            //2.1 获取当前字符的索引
            int index = prefix.charAt(i) - 'a';
            //2.2 判断当前字符是否存在
            if (current.nexts[index] == null) {    //不存在,直接返回0
                return 0;
            }else{
                current = current.nexts[index];    //移动到下一个节点
            }
        }
        return current.pass;    //返回pass值
    }


    @Test
    public void test() {
        PrefixTreeUtil prefixTreeUtil = new PrefixTreeUtil();
        prefixTreeUtil.initPrefixTree();
        prefixTreeUtil.insert("abc");
        prefixTreeUtil.insert("abcd");
        prefixTreeUtil.insert("ab");
        prefixTreeUtil.insert("ab");
        prefixTreeUtil.insert("abd");
        System.out.println(prefixTreeUtil.query("abc")); //1
        System.out.println(prefixTreeUtil.query("abcd")); //1
        System.out.println(prefixTreeUtil.query("ab")); //2
        System.out.println(prefixTreeUtil.queryPrefix("a"));//5
        prefixTreeUtil.delete("ab");
        System.out.println(prefixTreeUtil.query("ab"));
        System.out.println(prefixTreeUtil.query("abd"));
        prefixTreeUtil.delete("abd");
        System.out.println(prefixTreeUtil.query("abd"));
    }









}
